package com.zhengwl.study.sort;

import java.util.Arrays;

import javax.xml.crypto.Data;

public class InsertSort implements Sort {

	private SortType sortType;

	public InsertSort() {
		sortType = SortType.InsertSort;
	}

	@Override
	public void sort(int[] items) {
		if (sortType == SortType.InsertSort) {
			insertSort(items);
		} else if (sortType == SortType.ShellSort) {
			shellSort(items);
		} else {
			binaryInsertSort(items);
		}
	}

	// 直接插入排序，将第n个元素，插入到前面的有序子序列中
	public void insertSort(int[] items) {
		for (int i = 1; i < items.length; i++) {			
			int tmp = items[i];
			if(items[i-1]>items[i]){
				int j = 0;
				//整体后移一格
				for (j = i - 1; j >= 0 && items[j] > tmp; j--) {
					items[j + 1] = items[j];
				}
				//将tmp值插到合适位置
				items[j + 1] = tmp;
			}
			System.out.println(Arrays.toString(items));
		}

	}

	public void binaryInsertSort(int[] items) {
		for (int i = 1; i < items.length; i++) {
			int j = 0;
			int tmp = items[i];
			for (j = i - 1; j >= 0 && items[j] > tmp; j--) {
				items[j + 1] = items[j];
			}
			items[j + 1] = tmp;
			System.out.println(Arrays.toString(items));
		}

	}

	//希尔排序：
	public void shellSort(int[] items) {
		for (int i = 1; i < items.length; i++) {
			int j = 0;
			int tmp = items[i];
			for (j = i - 1; j >= 0 && items[j] > tmp; j--) {
				items[j + 1] = items[j];
			}
			items[j + 1] = tmp;
			System.out.println(Arrays.toString(items));
		}

	}

}
